package com.example.dynamicprogramming42.practice;

/**
 * @description 课后练习，如何求出这个序列中的最长递增子序列长度？
 * 比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。
 * @auther lijiewei
 * @date 2022/5/18 14:04
 */
public class FlashBackPractice {


    private int[] a = {2, 9, 3, 6, 5, 1, 7};

    private int n = 7;

    private int maxSonLength = Integer.MIN_VALUE;

    public int getMaxSonLength() {
        sonIndex(0, 0, 0);
        return maxSonLength;
    }

    /**
     * 回溯算法
     * @param i 慢指针
     * @param j 快指针
     * @param sonLength 当前最长递增子序列长度
     * @return
     * @author lijiewei
     * @date   2022/5/18 15:32
     */
    private void sonIndex(int i, int j, int sonLength) {
        //已经对比完了所有数据
        if (i==n || j==n) {
            if (sonLength > maxSonLength) {
                maxSonLength = sonLength;
            }
            return;
        }
        //回溯的处理思路
        //(i,j)从（0,0）开始依次对比
        //如果a[i]<a[j], 有两个不同策略：
        // 1.最长递增子序列长度加一，继续比较a[j]与a[j+1]
        // 2.最长递增子序列长度不变，继续比较a[i]与a[j+1]
        // 3.最长递增子序列长度不变，继续比较a[i+1]与a[j+1]
        //如果a[i]>=a[j], 有两个不同策略：
        // 1.最长递增子序列长度不变，继续比较a[i]与a[j+1]
        // 2.最长递增子序列长度不变，继续比较a[i+1]与a[j+1]
        if (a[i] < a[j]) {
            if (sonLength == 0) {
                sonIndex(j, j+1, sonLength+2);
            } else {
                sonIndex(j, j+1, sonLength+1);
            }
        }
        sonIndex(i, j+1, sonLength);
        sonIndex(i+1, j+1, sonLength);
    }

    //记录下标对应的最长递增子序列长度
    int[] state = new int[n];
    public int getMaxSonLength2() {
        state[0] = 1;
        for (int i = 1; i < n; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) {
                    max = state[j] > max ? state[j] : max;
                }
            }
            //
            state[i] = max+1;
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = state[i] > result ? state[i] : result;
        }
        return result;
    }



}
